import java.util.ArrayList;

public class PRQuadTree<E> {
	private final int MAX_BUCKET_SIZE = 3;

	// private enums
	private enum Quadrant {
		NW, NE, SW, SE, ROOT
	};

	private enum Command {
		Insert, Remove
	};

	/**
	 * Class to manage and compare coordinates
	 */
	private class Coordinates {
		public int x, y;

		public Coordinates(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public int getXCoord() {
			return x;
		}

		public int getYCoord() {
			return y;
		}

		public boolean equals(Coordinates coord) {
			if (x == coord.x && y == coord.y)
				return true;
			return false;
		}
	}

	/**
	 * abstract QuadNode base class
	 * 
	 */
	private abstract class prQuadNode {
		private prQuadInternal parent = null;

		public abstract boolean isLeaf();

		public prQuadInternal getParent() {
			return parent;
		}

		public prQuadNode setParent(prQuadInternal parent) {
			this.parent = parent;
			return this;
		}

		public abstract int size();

		public abstract void printData();
	}

	/**
	 * internal node implementation
	 * 
	 */
	private class prQuadInternal extends prQuadNode {
		private prQuadNode NE;
		private prQuadNode NW;
		private prQuadNode SE;
		private prQuadNode SW;

		public boolean isLeaf() {
			return false;
		}

		public prQuadNode getNE() {
			return NE;
		}

		public void setNE(prQuadNode nE) {
			NE = nE;
		}

		public prQuadNode getNW() {
			return NW;
		}

		public void setNW(prQuadNode nW) {
			NW = nW;
		}

		public prQuadNode getSE() {
			return SE;
		}

		public void setSE(prQuadNode sE) {
			SE = sE;
		}

		public prQuadNode getSW() {
			return SW;
		}

		public void setSW(prQuadNode sW) {
			SW = sW;
		}

		public int size() {
			return NE.size() + NW.size() + SE.size() + SW.size();
		}

		public final void printData() {
			System.out.print("I");
			System.out.flush();
			NW.printData();
			NE.printData();
			SW.printData();
			SE.printData();
		}
	}

	/**
	 * leaf node implementation
	 * 
	 */
	private class prQuadLeaf extends prQuadNode {
		public ArrayList<E> elements = new ArrayList<E>();
		public ArrayList<Coordinates> coordinates = new ArrayList<Coordinates>();

		public boolean isLeaf() {
			return true;
		}

		public int size() {
			return elements.size();
		}

		public final void printData() {
			if (elements.size() == 0) {
				System.out.print("E");
				System.out.flush();
			}
			else {
				for (int i = 0; i < elements.size(); i++) {
					System.out.print(elements.get(i).toString() + "|");
					System.out.flush();
				}
			}
		}
	}

	/**
	 * private members
	 */
	private prQuadNode root;
	private int xMin, xMax, yMin, yMax;
	private prQuadLeaf emptyLeaf = new prQuadLeaf();

	/**
	 * Constructor
	 * 
	 * @param xMin Low x boundary
	 * @param xMax High x boundary
	 * @param yMin Low y boundary
	 * @param yMax High y boundary
	 */
	public PRQuadTree(int xMin, int xMax, int yMin, int yMax) {
		this.xMin = xMin;
		this.xMax = xMax;
		this.yMin = yMin;
		this.yMax = yMax;

		if (xMin >= xMax || yMin >= yMax)
			throw new IndexOutOfBoundsException();
		clear();
	}

	/**
	 * Insert the given element at coordinates (x, y)
	 * 
	 * @param element 	object to be inserted
	 * @param x 		x coordinate to be inserted
	 * @param y			y coordinate to be inserted
	 * @return			true if object was inserted properly, false otherwise
	 */
	public boolean insert(E element, int x, int y) {
		// check given coordinates
		if (x < xMin || x >= xMax || y < yMin || y >= yMax) {
			return false;
		}

		Coordinates coord = new Coordinates(x, y);

		try {
			findHelper(root, element, coord, xMin, xMax, yMin, yMax,
					Quadrant.ROOT, Command.Insert);
		} catch (Exception err) {
			return false;
		}

		return true;
	}

	@SuppressWarnings("unchecked")
	/**
	 * Private helper method for insert and remove
	 */
	private prQuadLeaf findHelper(prQuadNode sRoot, E elem, Coordinates coord,
			int xLow, int xHi, int yLow, int yHi, Quadrant quad, Command command)
			throws Exception {
		prQuadNode result = sRoot;
		Quadrant targetQuad;
		int xMi, xMa, yMi, yMa;

		// find correct quadrant for coordinates.
		if (!result.isLeaf()) {
			if (coord.getXCoord() < (xLow + ((xHi - xLow) / 2))) {
				xMi = xLow;
				xMa = (xLow + (xHi - xLow) / 2);
				// NW
				if (coord.getYCoord() < (yLow + ((yHi - yLow) / 2))) {
					targetQuad = Quadrant.NW;
					yMi = yLow;
					yMa = yLow + (yHi - yLow) / 2;
				}
				// SW
				else {
					targetQuad = Quadrant.SW;
					yMi = yHi - (yHi - yLow) / 2;
					yMa = yHi;
				}
			} else {
				xMi = xHi - (xHi - xLow) / 2;
				xMa = xHi;
				// NE
				if (coord.getYCoord() < (yLow + ((yHi - yLow) / 2))) {
					targetQuad = Quadrant.NE;
					yMi = yLow;
					yMa = yLow + (yHi - yLow) / 2;
				}
				// SE
				else {
					targetQuad = Quadrant.SE;
					yMi = yHi - (yHi - yLow) / 2;
					yMa = yHi;
				}
			}

			prQuadNode targetNode = sRoot;

			// retrieve the target node to check for flyweight
			switch (targetQuad) {
			case NW:
				targetNode = ((prQuadInternal) sRoot).getNW();
				break;
			case SW:
				targetNode = ((prQuadInternal) sRoot).getSW();
				break;
			case NE:
				targetNode = ((prQuadInternal) sRoot).getNE();
				break;
			case SE:
				targetNode = ((prQuadInternal) sRoot).getSE();
				break;
			}

			// if the child is a flyweight and quadtree is inserting, replace it
			if (command == Command.Insert && targetNode == emptyLeaf) {
				prQuadLeaf leaf = new prQuadLeaf();
				leaf.setParent((prQuadInternal) sRoot);

				switch (targetQuad) {
				case NW:
					((prQuadInternal) sRoot).setNW(leaf);
					break;
				case SW:
					((prQuadInternal) sRoot).setSW(leaf);
					break;
				case NE:
					((prQuadInternal) sRoot).setNE(leaf);
					break;
				case SE:
					((prQuadInternal) sRoot).setSE(leaf);
					break;
				}
				targetNode = leaf;
			}

			result = findHelper(targetNode, elem, coord, xMi, xMa, yMi, yMa,
					targetQuad, command);
		} else if (command == Command.Insert) { // insert the given element
			prQuadLeaf bucket = (prQuadLeaf) sRoot;
			if (bucket.elements.size() < MAX_BUCKET_SIZE) {
				if (!checkCoordinates(coord, bucket)
						&& command == Command.Insert)
					throw new java.lang.Exception(
							"Record already exists at given coordinates.");
				bucket.elements.add(elem);
				bucket.coordinates.add(coord);
			} else { // create a new internal node with quadrants
				prQuadInternal parent = bucket.getParent();

				// make a new internal node
				prQuadInternal internal = new prQuadInternal();
				internal.setParent(parent);
				internal.setNW(emptyLeaf);
				internal.setNE(emptyLeaf);
				internal.setSW(emptyLeaf);
				internal.setSE(emptyLeaf);

				// handle root = leaf case
				if (bucket == root) {
					root = internal;
				} else {
					switch (quad) {
					case NW:
						parent.setNW(internal);
						break;
					case NE:
						parent.setNE(internal);
						break;
					case SW:
						parent.setSW(internal);
						break;
					case SE:
						parent.setSE(internal);
						break;
					}
				}

				// insert the elements of the previously existing bucket
				for (int i = 0; i < bucket.elements.size(); i++) {
					E element = bucket.elements.remove(i);
					Coordinates temp = bucket.coordinates.remove(i);
					// insert (element, temp.getXCoord(), temp.getYCoord());
					findHelper(internal, element, temp, xLow, xHi, yLow, yHi,
							quad, Command.Insert);
				}
				
				
				// insert the initially intended element
				findHelper(internal, elem, coord, xLow, xHi, yLow, yHi, quad, Command.Insert);
			}
		}

		// base case: node passed in is a leaf node
		return (prQuadLeaf) result;
	}

	/**
	 * Remove any element at the given coordinates (x, y)
	 * @param x
	 * @param y
	 * @return the removed element
	 */
	public E remove(int x, int y) {
		// check given coordinates
		if (x < xMin || x > xMax || y < yMin || y > yMax) {
			System.err
					.println("Quadtree: Remove called on invalid coordinates.\n");
			return null;
		}

		Coordinates coord = new Coordinates(x, y);
		E elem = null;

		prQuadLeaf targetBucket = null;
		try {
			targetBucket = findHelper(root, elem, coord, xMin, xMax, yMin,
					yMax, Quadrant.ROOT, Command.Remove);
		} catch (Exception e) {
			return null;
		}

		boolean found = false;
		int index = -1;
		
		// check the bucket for given coordinates
		for (Coordinates c : targetBucket.coordinates) {
			if (coord.equals(c)) {
				found = true;
				index = targetBucket.coordinates.indexOf(c);
			}
		}

		// remove the element and its coordinates from the bucket
		if (found) {
			elem = targetBucket.elements.remove(index);
			targetBucket.coordinates.remove(index);

			// check the bucket's ancestors to see if nodes can be merged
			prQuadInternal ancestor = targetBucket.getParent();
	
			if (ancestor != null) {
				// traverse up the tree until the size threshold is reached
				while (ancestor.getParent() != null && ancestor.size() <= MAX_BUCKET_SIZE)
					ancestor = ancestor.getParent();
	
				mergeChildren(ancestor);
			}
		}

		return elem;
	}

	/**
	 * Clear the tree
	 */
	public void clear() {
		root = emptyLeaf;
	}

	@SuppressWarnings("unchecked")
	/**
	 * Helper method to merge the children buckets into a single bucket
	 * when removing an element brings the number of elements in an internal 
	 * node below the maximum bucket size.
	 * 
	 * @param node Internal node to be merged.
	 * @return the resulting leaf node
	 */
	private prQuadLeaf mergeChildren(prQuadNode node) {
		if (node.isLeaf()) {
			return (prQuadLeaf) node;
		} else {
			prQuadLeaf result = new prQuadLeaf();
			result.setParent((prQuadInternal) node);
			result.elements.addAll(mergeChildren(((prQuadInternal) node)
					.getNE()).elements);
			result.coordinates.addAll(mergeChildren(((prQuadInternal) node)
					.getNE()).coordinates);
			result.elements.addAll(mergeChildren(((prQuadInternal) node)
					.getNW()).elements);
			result.coordinates.addAll(mergeChildren(((prQuadInternal) node)
					.getNW()).coordinates);
			result.elements.addAll(mergeChildren(((prQuadInternal) node)
					.getSE()).elements);
			result.coordinates.addAll(mergeChildren(((prQuadInternal) node)
					.getSE()).coordinates);
			result.elements.addAll(mergeChildren(((prQuadInternal) node)
					.getSW()).elements);
			result.coordinates.addAll(mergeChildren(((prQuadInternal) node)
					.getSW()).coordinates);

			return result;
		}
	}

	/**
	 * Check if the given coordinates are stored in the given bucket.
	 * 
	 * @param coord		target coordinates.
	 * @param bucket	bucket to search.
	 * @return	true if coord was found in bucket, false otherwise.
	 */
	private boolean checkCoordinates(Coordinates coord, prQuadLeaf bucket) {
		for (Coordinates c : bucket.coordinates) {
			if (c.equals(coord))
				return false;
		}
		return true;
	}

	// keep track of whether search found any results or not
	private boolean searchFound = false;
	
	/**
	 * Search a coordinate and radius around the point for any elements in the prQuadTree
	 *  
	 * @param x			x coordinate
	 * @param y			y coordinate
	 * @param radius	radius of search area
	 * @return	number of nodes traversed
	 */
	public int search(int x, int y, int radius) {
		searchFound = false;
		Coordinates coord = new Coordinates(x, y);
		int result = searchHelper(coord, radius, xMin, xMax, yMin, yMax, root);
		if (!searchFound) {
			System.out.println("No such record found.");
		}
		return result;
	}

	@SuppressWarnings("unchecked")
	/**
	 * Helper method to search a given area
	 */
	private int searchHelper(Coordinates coord, int radius, int xLow, int xHi,
			int yLow, int yHi, prQuadNode sRoot) {

		boolean overlaps = false;

		// check this node for overlap with the search radius
		if (coord.getXCoord() >= xLow && coord.getXCoord() < xHi
				&& coord.getYCoord() >= yLow && coord.getYCoord() < yHi) {
			overlaps = true;
		} else {
			// check all the boundaries to see if any part of the 
			ArrayList<Coordinates> boundaries = new ArrayList<Coordinates>();
			if (coord.getYCoord() >= yLow && coord.getYCoord() < yHi) {
				boundaries.add(new Coordinates(xLow, coord.getYCoord()));
				boundaries.add(new Coordinates(xHi - 1, coord.getYCoord()));
			}
			if (coord.getXCoord() >= xLow && coord.getXCoord() < xHi) {
				boundaries.add(new Coordinates(coord.getXCoord(), yLow));
				boundaries.add(new Coordinates(coord.getXCoord(), yHi - 1));
			}
			boundaries.add(new Coordinates(xLow, yLow));
			boundaries.add(new Coordinates(xHi - 1, yLow));
			boundaries.add(new Coordinates(xLow, yHi - 1));
			boundaries.add(new Coordinates(xHi - 1, yHi - 1));

			for (Coordinates c : boundaries) {
				if (overlaps)
					break;
				overlaps = radiusCheck(c, coord, radius);
			}
		}

		if (!overlaps)
			return 0;

		// overlapping leaf
		if (sRoot.isLeaf()) {
			if (sRoot != emptyLeaf) {
				for (int i = 0; i < ((prQuadLeaf) sRoot).coordinates.size(); i++) {
					if (radiusCheck(((prQuadLeaf) sRoot).coordinates.get(i),
							coord, radius)) {
						searchFound = true;
						System.out.println(((prQuadLeaf) sRoot).elements.get(i));
					}
				}
			}

			return 1;
		} else {
			return searchHelper(coord, radius, xLow, xLow + ((xHi - xLow)/2),
											   yLow, yLow + ((yHi - yLow)/2), ((prQuadInternal)sRoot).getNW()) +
                   searchHelper(coord, radius, xLow, xLow + ((xHi - xLow)/2),
                		   					   yHi - ((yHi - yLow)/2), yHi, ((prQuadInternal)sRoot).getSW()) +
                   searchHelper(coord, radius, xHi - ((xHi - xLow)/2), xHi,
                		   					   yLow, yLow + ((yHi - yLow)/2), ((prQuadInternal)sRoot).getNE()) +
                   searchHelper(coord, radius, xHi - ((xHi - xLow)/2), xHi,		  
                		   					   yHi - ((yHi - yLow)/2), yHi, ((prQuadInternal)sRoot).getSE()) + 1;
		}
	}

	/**
	 * Helper method to check if two points are within a certain distance.
	 * 
	 * @param a			point a
	 * @param b			point b
	 * @param radius	maximum distance between a and b
	 * @return	true if a and b are within radius
	 */
	private boolean radiusCheck(Coordinates a, Coordinates b, int radius) {
		int xLen = java.lang.Math.abs(a.getXCoord() - b.getXCoord());
		int yLen = java.lang.Math.abs(a.getYCoord() - b.getYCoord());

		return ((int) java.lang.Math.sqrt(xLen * xLen + yLen * yLen) <= radius);
	}
	
	/**
	 * Traverse through and print the nodes of the tree.
	 */
	public void debug() {
		root.printData();
		System.out.println();
		System.out.flush();
	}
}
